{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strong Password Checker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: strongPasswordChecker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #强密码检验器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>满足以下条件的密码被认为是强密码：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>由至少 <code>6</code> 个，至多 <code>20</code> 个字符组成。</li>\n",
    "\t<li>包含至少 <strong>一个小写 </strong>字母，至少&nbsp;<strong>一个大写</strong> 字母，和至少&nbsp;<strong>一个数字</strong> 。</li>\n",
    "\t<li>不包含连续三个重复字符 (比如 <code>\"B<em><strong>aaa</strong></em>bb0\"</code> 是弱密码, 但是&nbsp;<code>\"B<em><strong>aa</strong></em>b<em><strong>a</strong></em>0\"</code> 是强密码)。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>password</code> ，返回&nbsp;<em>将 <code>password</code> 修改到满足强密码条件需要的最少修改步数。如果 <code>password</code> 已经是强密码，则返回 <code>0</code> 。</em></p>\n",
    "\n",
    "<p>在一步修改操作中，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>插入一个字符到 <code>password</code> ，</li>\n",
    "\t<li>从 <code>password</code> 中删除一个字符，或</li>\n",
    "\t<li>用另一个字符来替换 <code>password</code> 中的某个字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>password = \"a\"\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>password = \"aA1\"\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>password = \"1337C0d3\"\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= password.length &lt;= 50</code></li>\n",
    "\t<li><code>password</code> 由字母、数字、点 <code>'.'</code> 或者感叹号 <code>'!'</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strong-password-checker](https://leetcode.cn/problems/strong-password-checker/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strong-password-checker](https://leetcode.cn/problems/strong-password-checker/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"a\"', '\"aA1\"', '\"1337C0d3\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        if all(not w.islower() for w in password):\n",
    "            return False\n",
    "        if all(not w.isupper() for w in password):\n",
    "            return False\n",
    "\n",
    "        if all(not w.isnumeric() for w in password):\n",
    "            return False\n",
    "        if all(w not in \"!@#$%^&*()-+\" for w in password):\n",
    "            return False\n",
    "        n = len(password)\n",
    "        return all(password[i+1]!=password[i] for i in range(n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        pattern = r\"^(?=.*[a-z])(?=.*[A-Z])(?=.*\\d)(?=.*[!@#$%^&*()\\-+])[a-zA-Z\\d!@#$%^&*()\\-+]{8,}$\"\n",
    "        if re.match(pattern, password):\n",
    "        # 检查是否包含2个连续相同的字符\n",
    "            for i in range(len(password) - 1):\n",
    "                if password[i] == password[i + 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        l = [0, 0, 0, 0]\n",
    "        for i in range(len(password)):\n",
    "            if i < len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                l[2] += 1\n",
    "            if ord('a') <= ord(password[i]) <= ord('z'):\n",
    "                l[1] += 1\n",
    "            if ord('A') <= ord(password[i]) <= ord('Z'):\n",
    "                l[0] += 1\n",
    "            if ord('0') <= ord(password[i]) <= ord('9'):\n",
    "                l[3] += 1\n",
    "        print(l)\n",
    "        return l[0] * l[1] * l[2] * l[3] > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "#         diclower = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "#         dicupper = diclower.upper()\n",
    "#         dicnum = \"1234567890\"\n",
    "#         dicspecial = \"!@#$%^&*()-+\"\n",
    "#         def check(dic, i):\n",
    "#             for j in dic:\n",
    "#                 if j in i:\n",
    "#                     return True\n",
    "#         def doublecheck(i):\n",
    "#             for n in range(len(i)-1):\n",
    "#                 if i[n] == i[n+1]:\n",
    "#                     return False\n",
    "#             return True\n",
    "#         if len(password)>=8 and check(diclower, password) and check(dicupper, password) and check(dicnum, password) and check(dicspecial, password) and doublecheck(password):\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        special_s = '!@#$%^&*()-+'\n",
    "        n = len(password)\n",
    "        if n < 8: return False\n",
    "        flag1, flag2, flag3, flag4 = False, False, False, False\n",
    "        for i in range(n):\n",
    "            if 'a' <= password[i] <= 'z':\n",
    "                flag1 = True\n",
    "            elif 'A' <= password[i] <= 'Z':\n",
    "                flag2 = True\n",
    "            elif '0' <= password[i] <= '9':\n",
    "                flag3 = True\n",
    "            elif password[i] in special_s:\n",
    "                flag4 = True\n",
    "            if i and password[i] == password[i-1]:\n",
    "                return False\n",
    "        return flag1 and flag2 and flag3 and flag4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        res = [0]*6\n",
    "        if len(password)<8:res[0] = 0\n",
    "        else:res[0] = 1\n",
    "        albet = \"!@#$%^&*()-+\"\n",
    "        for i in range(len(password)):\n",
    "            if password[i].islower():res[1] = 1\n",
    "            elif password[i].isupper():res[2] = 1\n",
    "            elif password[i].isalnum():res[3] = 1\n",
    "            elif password[i] in albet:res[4] = 1\n",
    "        for i in range(1,len(password)):\n",
    "            if password[i-1]==password[i]:\n",
    "                return False\n",
    "            else:res[5] = 1\n",
    "        return sum(res) == 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        mask = 0\n",
    "        for i, c in enumerate(password):\n",
    "            if i and c == password[i - 1]:\n",
    "                return False\n",
    "            if c.islower():\n",
    "                mask |= 1\n",
    "            elif c.isupper():\n",
    "                mask |= 2\n",
    "            elif c.isdigit():\n",
    "                mask |= 4\n",
    "            else:\n",
    "                mask |= 8\n",
    "        return mask == 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, p: str) -> bool:\n",
    "        if len(p)<8: \n",
    "            return False\n",
    "        a = [0,0,0,0,1]\n",
    "        for ch in p:\n",
    "            if 'a'<=ch<='z':\n",
    "                a[0]=1\n",
    "            if 'A'<=ch<='Z':\n",
    "                a[1]=1\n",
    "            if '0'<=ch<='9':\n",
    "                a[2]=1\n",
    "            if ch in '!@#$%^&*()-+':\n",
    "               a[3]=1\n",
    "        i = 0 \n",
    "        while i<len(p)-1:\n",
    "            if p[i]==p[i+1]: a[4]=0\n",
    "            i += 1\n",
    "        # print(a)\n",
    "        return sum(a)==5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if(len(password)<8):\n",
    "            return False\n",
    "        for i in range(len(password)-1):\n",
    "            if(password[i] == password[i+1]):\n",
    "                return False\n",
    "        lowercase = set('qazwsxedcrfvtgbyhnujmikolp')\n",
    "        upercase = set('QAZWSXEDCRFVTGBYHNUJMIKOLP')\n",
    "        num = set('1234567890')\n",
    "        char = set('!@#$%^&*()-+')\n",
    "        password = set(password)\n",
    "        if not(password & lowercase):\n",
    "            return False\n",
    "        if not(password & upercase):\n",
    "            return False\n",
    "        if not(password & num):\n",
    "            return False\n",
    "        if not(password & char):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        pattern = r\"^(?=.*[a-z])(?=.*[A-Z])(?=.*\\d)(?=.*[!@#$%^&*()\\-+])[a-zA-Z\\d!@#$%^&*()\\-+]{8,}$\"\n",
    "        if re.match(pattern, password):\n",
    "        # 检查是否包含2个连续相同的字符\n",
    "            for i in range(len(password) - 1):\n",
    "                if password[i] == password[i + 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, p: str) -> bool:\n",
    "        if len(p)<8: return False\n",
    "        a = [0,0,0,0,1]\n",
    "        for ch in p:\n",
    "            if 'a'<=ch<='z': a[0]=1\n",
    "            if 'A'<=ch<='Z': a[1]=1\n",
    "            if '0'<=ch<='9': a[2]=1\n",
    "            if ch in '!@#$%^&*()-+': a[3]=1\n",
    "        i = 0 \n",
    "        while i<len(p)-1:\n",
    "            if p[i]==p[i+1]: a[4]=0\n",
    "            i += 1\n",
    "        # print(a)\n",
    "        return sum(a)==5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        low_mark=False\n",
    "        up_mark=False\n",
    "        int_mark=False\n",
    "        set_mark=False\n",
    "        str_set=\"!@#$%^&*()-+\"\n",
    "        for i in range(n):\n",
    "            if i-1 >= 0 and password[i] == password[i-1]: return False\n",
    "            elif password[i].islower():low_mark=True\n",
    "            elif password[i].isupper():up_mark=True\n",
    "            elif password[i].isdigit():int_mark=True\n",
    "            elif password[i] in str_set:set_mark=True\n",
    "        return low_mark&up_mark&int_mark&set_mark\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        \n",
    "        specials = set(\"!@#$%^&*()-+\")\n",
    "        hasLower = hasUpper = hasDigit = hasSpecial = False\n",
    "\n",
    "        for i, ch in enumerate(password):\n",
    "            if i != len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "\n",
    "            if ch.islower():\n",
    "                hasLower = True\n",
    "            elif ch.isupper():\n",
    "                hasUpper = True\n",
    "            elif ch.isdigit():\n",
    "                hasDigit = True\n",
    "            elif ch in specials:\n",
    "                hasSpecial = True\n",
    "\n",
    "        return hasLower and hasUpper and hasDigit and hasSpecial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if(len(password)<8):\n",
    "            return False\n",
    "        for i in range(len(password)-1):\n",
    "            if(password[i] == password[i+1]):\n",
    "                return False\n",
    "        lowercase = set('qazwsxedcrfvtgbyhnujmikolp')\n",
    "        upercase = set('QAZWSXEDCRFVTGBYHNUJMIKOLP')\n",
    "        num = set('1234567890')\n",
    "        char = set('!@#$%^&*()-+')\n",
    "        password = set(password)\n",
    "        if not(password & lowercase):\n",
    "            return False\n",
    "        if not(password & upercase):\n",
    "            return False\n",
    "        if not(password & num):\n",
    "            return False\n",
    "        if not(password & char):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if (len(password) < 8 or \n",
    "            all(not c.islower() for c in password) or \n",
    "            all(not c.islower() for c in password) or \n",
    "            all(not c.isupper() for c in password) or \n",
    "            all(not c.isdigit()  for c in password) or \n",
    "            all(c not in set(\"!@#$%^&*()-+\") for c in password) or \n",
    "            any(password[i] == password[i+1] for i in range(len(password)-1))):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        for i in range(1,len(password)):\n",
    "            if password[i] == password[i-1]:\n",
    "                return False\n",
    "        f1,f2,f3,f4 = False,False,False,False\n",
    "        for i in range(len(password)):\n",
    "            if ord(password[i]) >= 65 and ord(password[i]) <= 90:\n",
    "                f1 = True\n",
    "            if ord(password[i]) >= 97 and ord(password[i]) <= 122:\n",
    "                f2 = True\n",
    "            if password[i] in '0123456789':\n",
    "                f3 = True\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                f4 = True\n",
    "        return f1&f2&f3&f4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        SpeChar = '!@#$%^&*()-+'\n",
    "        islower = False\n",
    "        isUpper = False\n",
    "        isDigit = False\n",
    "        isSpecial = False\n",
    "        preChar = password[1]\n",
    "        for i in password:\n",
    "            if i == preChar:\n",
    "                return False\n",
    "            preChar = i\n",
    "            if i.islower():\n",
    "                islower = True\n",
    "            elif i.isupper():\n",
    "                isUpper = True\n",
    "            elif i.isdigit():\n",
    "                isDigit = True\n",
    "            elif i in SpeChar:\n",
    "                isSpecial = True\n",
    "        return islower and isUpper and isDigit and isSpecial\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        \n",
    "        specials = set(\"!@#$%^&*()-+\")\n",
    "        hasLower = hasUpper = hasDigit = hasSpecial = False\n",
    "\n",
    "        for i, ch in enumerate(password):\n",
    "            if i != len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "\n",
    "            if ch.islower():\n",
    "                hasLower = True\n",
    "            elif ch.isupper():\n",
    "                hasUpper = True\n",
    "            elif ch.isdigit():\n",
    "                hasDigit = True\n",
    "            elif ch in specials:\n",
    "                hasSpecial = True\n",
    "\n",
    "        return hasLower and hasUpper and hasDigit and hasSpecial\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        x,y,z,a = 0,0,0,0\n",
    "        l1 = {\"!\",\"@\",\"#\",\"$\",\"%\",\"^\",\"&\",\"*\",\"(\",\")\",\"-\",\"+\"}\n",
    "        for i in range (len(password) - 1):\n",
    "            if password[i].islower():\n",
    "                x += 1\n",
    "            if password[i].isupper():\n",
    "                y += 1\n",
    "            if password[i].isdigit():\n",
    "                z += 1\n",
    "            if password[i] in l1:\n",
    "                a += 1\n",
    "            if password[i] == password[i + 1]:\n",
    "                return False\n",
    "        if password[-1].islower():\n",
    "            x += 1\n",
    "        if password[-1].isupper():\n",
    "            y += 1\n",
    "        if password[-1].isdigit():\n",
    "            z += 1\n",
    "        if password[-1] in l1:\n",
    "            a += 1\n",
    "        if x * y * z * a == 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8: return False\n",
    "        letter_upper = False\n",
    "        letter_lower = False\n",
    "        digit = False\n",
    "        special = False\n",
    "        specials = '!@#$%^&*()-+'\n",
    "        tmp = ''\n",
    "        for word in password:\n",
    "            if tmp == '':\n",
    "                tmp = word\n",
    "            else:\n",
    "                if tmp == word:\n",
    "                    return False\n",
    "                else:\n",
    "                    tmp = word\n",
    "            if word.isupper(): \n",
    "                letter_upper = True\n",
    "                continue\n",
    "            elif word.islower():\n",
    "                letter_lower = True\n",
    "                continue\n",
    "            elif word.isdigit():\n",
    "                digit = True\n",
    "                continue\n",
    "            elif word in specials:\n",
    "                special = True\n",
    "        return True if letter_upper and letter_lower and digit and special else False\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        x,y,z,a = 0,0,0,0\n",
    "        l1 = {\"!\",\"@\",\"#\",\"$\",\"%\",\"^\",\"&\",\"*\",\"(\",\")\",\"-\",\"+\"}\n",
    "        for i in range (len(password) - 1):\n",
    "            if password[i].islower():\n",
    "                x += 1\n",
    "            if password[i].isupper():\n",
    "                y += 1\n",
    "            if password[i].isdigit():\n",
    "                z += 1\n",
    "            if password[i] in l1:\n",
    "                a += 1\n",
    "            if password[i] == password[i + 1]:\n",
    "                return False\n",
    "        if password[-1].islower():\n",
    "            x += 1\n",
    "        if password[-1].isupper():\n",
    "            y += 1\n",
    "        if password[-1].isdigit():\n",
    "            z += 1\n",
    "        if password[-1] in l1:\n",
    "            a += 1\n",
    "        if x * y * z * a == 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "\n",
    "        if n<8:\n",
    "            return False\n",
    "        \n",
    "        judge1 = [password[i].isupper() for i in range(n)]\n",
    "        if any(judge1)==False:\n",
    "            return False\n",
    "        \n",
    "        judge2 = [password[i].islower() for i in range(n)]\n",
    "        if any(judge2)==False:\n",
    "            return False\n",
    "        \n",
    "        judge3 = [password[i].isnumeric() for i in range(n)]\n",
    "        if any(judge3)==False:\n",
    "            return False\n",
    "        \n",
    "        secret = \"!@#$%^&*()-+\"\n",
    "\n",
    "        judge4 = [password[i] in secret for i in range(n)]\n",
    "        if any(judge4)==False:\n",
    "            return False\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if password[i-1] == password[i]:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        password = list(password)\n",
    "        small = 0\n",
    "        upper = 0\n",
    "        num = 0\n",
    "        repeat = 0\n",
    "        unique = ['!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '+']\n",
    "        uni = 0\n",
    "        if len(password) >= 8:\n",
    "            for i in password:\n",
    "                if ord(i) in range(65, 91):\n",
    "                    upper += 1\n",
    "                if ord(i) in range(97, 123):\n",
    "                    small += 1\n",
    "                if ord(i) in range(48, 58):\n",
    "                    num += 1\n",
    "                if i != password[-1] and i == password[password.index(i)+1]:\n",
    "                    repeat += 1\n",
    "                if i in unique:\n",
    "                    uni += 1\n",
    "        if small >= 1 and upper >= 1 and num >= 1 and repeat == 0 and uni >= 1:\n",
    "            return True\n",
    "\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        small_e = False\n",
    "        big_e = False\n",
    "        num = False\n",
    "        special = False\n",
    "        last = ''\n",
    "        for c in password:\n",
    "            if  c.isdigit():\n",
    "                num = True\n",
    "            elif c.islower():\n",
    "                small_e = True\n",
    "            elif c.isupper():\n",
    "                big_e = True\n",
    "            elif c in \"!@#$%^&*()-+\":\n",
    "                special = True\n",
    "            if last == c:\n",
    "                return False\n",
    "            last = c\n",
    "        return num and small_e and big_e and special"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        l = [0, 0, 0, 0]\n",
    "        for i in range(len(password)):\n",
    "            if i < len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                l[2] += 1\n",
    "            if ord('a') <= ord(password[i]) <= ord('z'):\n",
    "                l[1] += 1\n",
    "            if ord('A') <= ord(password[i]) <= ord('Z'):\n",
    "                l[0] += 1\n",
    "            if ord('0') <= ord(password[i]) <= ord('9'):\n",
    "                l[3] += 1\n",
    "        print(l)\n",
    "        return l[0] * l[1] * l[2] * l[3] > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        \n",
    "        specials = set(\"!@#$%^&*()-+\")\n",
    "        hasLower = hasUpper = hasDigit = hasSpecial = False\n",
    "\n",
    "        for i, ch in enumerate(password):\n",
    "            if i != len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "\n",
    "            if ch.islower():\n",
    "                hasLower = True\n",
    "            elif ch.isupper():\n",
    "                hasUpper = True\n",
    "            elif ch.isdigit():\n",
    "                hasDigit = True\n",
    "            elif ch in specials:\n",
    "                hasSpecial = True\n",
    "\n",
    "        return hasLower and hasUpper and hasDigit and hasSpecial\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) >= 8 and password.upper()!=password and password.lower()!=password:\n",
    "          sign1 = False\n",
    "          sign2 = False\n",
    "          for i in password:\n",
    "              if i in [str(l) for l in range(0,10)]:\n",
    "                  sign1  = True\n",
    "              if i in \"!@#$%^&*()-+\":\n",
    "                  sign2  = True\n",
    "              if sign1 and sign2:break\n",
    "          print(sign1,sign2)\n",
    "          if sign1 and sign2:\n",
    "              for j in range(1,len(password)):\n",
    "                    if password[j] == password[j-1]:\n",
    "                        return False\n",
    "              return True;\n",
    "          else:\n",
    "              return False\n",
    "          \n",
    "                  \n",
    "        else:\n",
    "            return False  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        lowerCnt = upperCnt = digitCnt = sepCnt = 0\n",
    "        speStr = '!@#$%^&*()-+'\n",
    "        pre = ''\n",
    "        preCnt = 0\n",
    "        for c in password:\n",
    "            if c == pre:\n",
    "                preCnt += 1\n",
    "                if preCnt >= 2:\n",
    "                    return False\n",
    "            pre = c\n",
    "            preCnt = 1\n",
    "            if c.islower():\n",
    "                lowerCnt += 1\n",
    "            elif c.isupper():\n",
    "                upperCnt += 1\n",
    "            elif c.isdigit():\n",
    "                digitCnt += 1\n",
    "            elif c in speStr:\n",
    "                sepCnt += 1\n",
    "        return lowerCnt >= 1 and upperCnt >= 1 and digitCnt >= 1 and sepCnt >= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        l = [0, 0, 0, 0]\n",
    "        for i in range(len(password)):\n",
    "            if i < len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                l[2] += 1\n",
    "            if ord('a') <= ord(password[i]) <= ord('z'):\n",
    "                l[1] += 1\n",
    "            if ord('A') <= ord(password[i]) <= ord('Z'):\n",
    "                l[0] += 1\n",
    "            if ord('0') <= ord(password[i]) <= ord('9'):\n",
    "                l[3] += 1\n",
    "        print(l)\n",
    "        return l[0] * l[1] * l[2] * l[3] > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        xiao = 0\n",
    "        da = 0\n",
    "        num = 0\n",
    "        s = 0\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        for i in password:\n",
    "            if xiao == 0 and 'a' <= i <= 'z':\n",
    "                xiao = 1\n",
    "            if da == 0 and 'A' <= i <= 'Z':\n",
    "                da = 1\n",
    "            if num == 0 and '0' <= i <= '9':\n",
    "                num = 1\n",
    "            if s == 0 and i in \"!@#$%^&*()-+\":\n",
    "                s = 1\n",
    "        for i in range(len(password)-1):\n",
    "            if password[i] == password[i+1]:\n",
    "                return False\n",
    "        if xiao ==1 and da == 1 and num == 1 and s == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        s = set(password)\n",
    "        if not s & set(string.ascii_lowercase):\n",
    "            return False\n",
    "        if not s & set(string.ascii_uppercase):\n",
    "            return False\n",
    "        if not s & set(string.digits):\n",
    "            return False\n",
    "        if not s & set(\"!@#$%^&*()-+\"):\n",
    "            return False\n",
    "        for i in range(1, n):\n",
    "            if password[i] == password[i-1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        return  bool(len(password) >= 8 and\n",
    "                search(r'\\d', password) and\n",
    "                search(r'[a-z]', password) and\n",
    "                search(r'[A-Z]', password) and\n",
    "                search(r'[-!@#$%^&*()+]', password) and\n",
    "                not search(r'(.)\\1', password))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        diclower = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        dicupper = diclower.upper()\n",
    "        dicnum = \"1234567890\"\n",
    "        dicspecial = \"!@#$%^&*()-+\"\n",
    "        def check(dic, i):\n",
    "            for j in dic:\n",
    "                if j in i:\n",
    "                    return True\n",
    "        def doublecheck(i):\n",
    "            for n in range(len(i)-1):\n",
    "                if i[n] == i[n+1]:\n",
    "                    return False\n",
    "            return True\n",
    "        if len(password)>=8 and check(diclower, password) and check(dicupper, password) and check(dicnum, password) and check(dicspecial, password) and doublecheck(password):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, p: str) -> bool:\n",
    "        if len(p) < 8:\n",
    "            return False\n",
    "        smallFlag = False\n",
    "        bigFlag = False\n",
    "        numFlag = False\n",
    "        sFlag = False\n",
    "        for i, pi in enumerate(p):\n",
    "            if \"Z\" >= pi >= \"A\":\n",
    "                bigFlag = True\n",
    "            if \"z\" >= pi >= \"a\":\n",
    "                smallFlag = True\n",
    "            if \"9\" >= pi >= \"0\":\n",
    "                numFlag = True\n",
    "            if pi in \"!@#$%^&*()-+\":\n",
    "                sFlag = True\n",
    "            if i > 0 and p[i] == p[i - 1]:\n",
    "                return False\n",
    "        return smallFlag and bigFlag and numFlag and sFlag\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        x=\"!@#$%^&*()-+\"\n",
    "        y='0123456789'\n",
    "        a=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n",
    "        b=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']\n",
    "        return len(password)>=8 and any(i in x for i in password) and any(j in y for j in password) and any(i in a for i in password) and any (j in b for j in password) and all(password[i]!=password[i+1] for i in range(len(password)-1))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        return  bool(len(password) >= 8 and\n",
    "                search(r'\\d', password) and\n",
    "                search(r'[a-z]', password) and\n",
    "                search(r'[A-Z]', password) and\n",
    "                search(r'[!@#$%^&*()\\-+]', password) and\n",
    "                not search(r'(.)\\1', password))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        sp='!@#$%^&*()-+'\n",
    "        flaglower=False\n",
    "        flagupper=False\n",
    "        flagdigit=False\n",
    "        flagspecial=False\n",
    "        flagtwo=True\n",
    "        for i in range(len(password)):\n",
    "            if password[i].islower():\n",
    "                flaglower=True\n",
    "            if password[i].isupper():\n",
    "                flagupper=True\n",
    "            if password[i].isdigit():\n",
    "                flagdigit=True\n",
    "            if password[i] in sp:\n",
    "                flagspecial=True\n",
    "            if i+1<len(password) and password[i]==password[i+1]:\n",
    "                flagtwo=False\n",
    "        flag=flaglower and flagupper and flagdigit and flagspecial and flagtwo and len(password)>=8\n",
    "        if flag:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        mask = 0\n",
    "        for i, c in enumerate(password):\n",
    "            if i and c == password[i - 1]:\n",
    "                return False\n",
    "            if c.islower():\n",
    "                mask |= 1\n",
    "            elif c.isupper():\n",
    "                mask |= 2\n",
    "            elif c.isdigit():\n",
    "                mask |= 4\n",
    "            else:\n",
    "                mask |= 8\n",
    "        return mask == 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "char = list(\"!@#$%^&*()-+\")\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        fo, ft, fs, ff, prev = False, False, False, False, password[1]\n",
    "        for s in password:\n",
    "            if prev == s:\n",
    "                return False\n",
    "            prev = s\n",
    "            if s.isupper():\n",
    "                fo = True\n",
    "            elif s.islower():\n",
    "                ft = True\n",
    "            elif ord(s) >= ord(\"0\") and ord(s) <= ord(\"9\"):\n",
    "                fs = True\n",
    "            elif s in char:\n",
    "                ff = True\n",
    "            \n",
    "        return fo and ft and fs and ff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "      if len(password) < 8:\n",
    "        return False\n",
    "      flag_lower = False\n",
    "      flag_upper = False\n",
    "      flag_one_digit = False\n",
    "      flag_special = False\n",
    "      flag_adjacent = True\n",
    "\n",
    "      for i in range(len(password)):\n",
    "        if password[i].islower():\n",
    "          flag_lower = True\n",
    "\n",
    "        if password[i].isupper():\n",
    "          flag_upper = True\n",
    "        \n",
    "        if password[i].isdigit():\n",
    "          flag_one_digit = True\n",
    "        \n",
    "        if not password[i].isdigit() and not password[i].isalpha():\n",
    "          flag_special = True\n",
    "        \n",
    "      for i in range(len(password) - 1):\n",
    "        if password[i] == password[i + 1]:\n",
    "          flag_adjacent = False\n",
    "        \n",
    "      return flag_lower and flag_upper and flag_one_digit and flag_special and flag_adjacent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "#         diclower = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "#         dicupper = diclower.upper()\n",
    "#         dicnum = \"1234567890\"\n",
    "#         dicspecial = \"!@#$%^&*()-+\"\n",
    "#         def check(dic, i):\n",
    "#             for j in dic:\n",
    "#                 if j in i:\n",
    "#                     return True\n",
    "#         def doublecheck(i):\n",
    "#             for n in range(len(i)-1):\n",
    "#                 if i[n] == i[n+1]:\n",
    "#                     return False\n",
    "#             return True\n",
    "#         if len(password)>=8 and check(diclower, password) and check(dicupper, password) and check(dicnum, password) and check(dicspecial, password) and doublecheck(password):\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        special_s = '!@#$%^&*()-+'\n",
    "        n = len(password)\n",
    "        if n < 8: return False\n",
    "        flag1, flag2, flag3, flag4 = False, False, False, False\n",
    "        for i in range(n):\n",
    "            if 'a' <= password[i] <= 'z':\n",
    "                flag1 = True\n",
    "            elif 'A' <= password[i] <= 'Z':\n",
    "                flag2 = True\n",
    "            elif '0' <= password[i] <= '9':\n",
    "                flag3 = True\n",
    "            elif password[i] in special_s:\n",
    "                flag4 = True\n",
    "            if i and password[i] == password[i-1]:\n",
    "                return False\n",
    "        return flag1 and flag2 and flag3 and flag4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        l = [0, 0, 0, 0]\n",
    "        for i in range(len(password)):\n",
    "            if i < len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                l[2] += 1\n",
    "            if ord('a') <= ord(password[i]) <= ord('z'):\n",
    "                l[1] += 1\n",
    "            if ord('A') <= ord(password[i]) <= ord('Z'):\n",
    "                l[0] += 1\n",
    "            if ord('0') <= ord(password[i]) <= ord('9'):\n",
    "                l[3] += 1\n",
    "        return l[0] * l[1] * l[2] * l[3] > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        have_uppper=False\n",
    "        have_lower=False\n",
    "        have_digit=False\n",
    "        have_sign=False\n",
    "        if len(password)<8:\n",
    "            return False\n",
    "        last=chr(ord(password[0])-1)\n",
    "        for s in password:\n",
    "            if s==last:\n",
    "                return False\n",
    "            elif s.isdigit():\n",
    "                have_digit=True\n",
    "            elif s in \"!@#$%^&*()-+\":\n",
    "                have_sign=True\n",
    "            elif s.islower():\n",
    "                have_lower=True\n",
    "            elif s.isupper():\n",
    "                have_uppper=True\n",
    "            last=s\n",
    "        return have_digit and have_lower and have_sign and have_uppper\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        special_pass = '!@#$%^&*()-+'\n",
    "        leng = len(password)\n",
    "        if leng < 8:\n",
    "            return False\n",
    "        flag1, flag2, flag3, flag4 = False, False, False, False\n",
    "        for i in range(leng):\n",
    "            if password[i].isupper():\n",
    "                flag1 = True\n",
    "            if password[i].islower():\n",
    "                flag2 = True\n",
    "            if password[i].isdigit():\n",
    "                flag3 = True\n",
    "            if password[i] in special_pass:\n",
    "                flag4 = True\n",
    "            if i and password[i] == password[i-1]:\n",
    "                return False\n",
    "        return flag1 and flag2 and flag3 and flag4\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        chars = \"!@#$%^&*()-+\"\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        a, b, c, d = False, False, False, False\n",
    "        for i in range(n):\n",
    "            if i > 0 and password[i] == password[i - 1]:\n",
    "                return False\n",
    "            if password[i].islower():\n",
    "                a = True\n",
    "            elif password[i].isupper():\n",
    "                b = True\n",
    "            elif password[i].isdigit():\n",
    "                c = True\n",
    "            elif password[i] in chars:\n",
    "                d = True\n",
    "        # if a == 0 or b == 0 or c == 0 or d == 0:\n",
    "        #     return False\n",
    "        return a and b and c and d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "\n",
    "        specials = set('!@#$%^&*()-+')\n",
    "        hasLower = hasUpper = hasDigit = hasSpecial = False\n",
    "\n",
    "        for i, ch in enumerate(password):\n",
    "            if i != len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            \n",
    "            if ch.islower():\n",
    "                hasLower = True\n",
    "            elif ch.isupper():\n",
    "                hasUpper = True\n",
    "            elif ch.isdigit():\n",
    "                hasDigit = True\n",
    "            elif ch in specials:\n",
    "                hasSpecial = True\n",
    "\n",
    "        return hasDigit and hasLower and hasSpecial and hasUpper "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 7:\n",
    "            return False\n",
    "        nums = set('1234567890')\n",
    "        spe = set(\"!@#$%^&*()-+\")\n",
    "        ans = [0,0,0,0,1]\n",
    "        for i in range(len(password)):\n",
    "            ordi = ord(password[i])\n",
    "            if i != 0 and password[i] == last:\n",
    "                ans[4] = 0\n",
    "            if 97<=ordi<=124:\n",
    "                ans[0] = 1\n",
    "            elif 65<=ordi<=91:\n",
    "                ans[1] = 1\n",
    "            elif password[i] in nums:\n",
    "                ans[2] = 1\n",
    "            elif password[i] in spe:\n",
    "                ans[3] = 1\n",
    "            last = password[i]\n",
    "        return ans == [1,1,1,1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "            d = []\n",
    "            if len(password) < 8:\n",
    "                return False\n",
    "\n",
    "            # while i <= length - 2:\n",
    "            #     if str[i] == str[i + 1]:\n",
    "            #         return False\n",
    "            #     else:\n",
    "            #         i += 1\n",
    "            s1 = ''\n",
    "            for s in password:\n",
    "                if s == s1:\n",
    "                    return False\n",
    "                else:\n",
    "                    s1 = s\n",
    "\n",
    "                # if len(d) == 4:\n",
    "                #     return True\n",
    "                # else:\n",
    "                #     pass\n",
    "\n",
    "                if s.isupper() and 'u' not in d:\n",
    "                    d.append('u')\n",
    "                elif s.islower() and 'l' not in d:\n",
    "                    d.append('l')\n",
    "                elif s.isdigit() and 'd' not in d:\n",
    "                    d.append('d')\n",
    "                elif s in '!@#$%^&*()-+' and 'c' not in d:\n",
    "                    d.append('c')\n",
    "\n",
    "            if len(d) < 4:\n",
    "                return False\n",
    "            else:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        for i in range(1,len(password)):\n",
    "            if password[i] == password[i-1]:\n",
    "                return False\n",
    "        f1,f2,f3,f4 = False,False,False,False\n",
    "        for i in range(len(password)):\n",
    "            if ord(password[i]) >= 65 and ord(password[i]) <= 90:\n",
    "                f1 = True\n",
    "            if ord(password[i]) >= 97 and ord(password[i]) <= 122:\n",
    "                f2 = True\n",
    "            if password[i] in '0123456789':\n",
    "                f3 = True\n",
    "            if password[i] in '!@#$%^&*()-+':\n",
    "                f4 = True\n",
    "        return f1&f2&f3&f4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        ans = 0\n",
    "        special_word = \"!@#$%^&*()-+\"\n",
    "        n = len(password)\n",
    "        if n < 8: return False\n",
    "        for i in range(n):\n",
    "            if i + 1 < n and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            if 'a' <= password[i] <= 'z':\n",
    "                ans |= 1\n",
    "            elif 'A' <= password[i] <= 'Z':\n",
    "                ans |= 1 << 1\n",
    "            elif '0' <= password[i] <= '9':\n",
    "                ans |= 1 << 2\n",
    "            elif password[i] in special_word:\n",
    "                ans |= 1 << 3\n",
    "        \n",
    "        return ans == 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        judge = {'l':0,'u':0,'d':0,'t':0}\n",
    "        for i in range(len(password)):\n",
    "            if i != 0 and password[i] == password[i-1]:\n",
    "                return False\n",
    "            if password[i].isalpha():\n",
    "                if password[i].islower():\n",
    "                    judge['l'] += 1\n",
    "                else:\n",
    "                    judge['u'] += 1\n",
    "            elif password[i].isdigit():\n",
    "                judge['d'] += 1\n",
    "            else:\n",
    "                judge['t'] += 1\n",
    "        for v in judge.values():\n",
    "            if v == 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        return  bool(len(password) >= 8 and\n",
    "                search(r'\\d', password) and\n",
    "                search(r'[a-z]', password) and\n",
    "                search(r'[A-Z]', password) and\n",
    "                search(r'[-!@#$%^&*()+]', password) and\n",
    "                not search(r'(.)\\1', password))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        return  bool(len(password) >= 8 and\n",
    "                search(r'\\d', password) and\n",
    "                search(r'[a-z]', password) and\n",
    "                search(r'[A-Z]', password) and\n",
    "                search(r'[!@#$%^&*()\\-+]', password) and\n",
    "                not search(r'(.)\\1', password))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password)<8:\n",
    "            return False\n",
    "        for i in range(len(password)-1):\n",
    "            if password[i]==password[i+1]:\n",
    "                return False\n",
    "        s=set(password)\n",
    "        return s&set('1234567890')!=set() and s&set('QWERTYUIOPASDFGHJKLZXCVBNM')!=set() and s&set('qwertyuiopasdfghjklzxcvbnm')!=set() and s&set('!@#$%^&*()-+')!=set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        chars = \"!@#$%^&*()-+\"\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        a, b, c, d = 0, 0, 0, 0\n",
    "        for i in range(n):\n",
    "            if password[i].islower():\n",
    "                a += 1\n",
    "            elif password[i].isupper():\n",
    "                b += 1\n",
    "            elif password[i].isdigit():\n",
    "                c += 1\n",
    "            elif password[i] in chars:\n",
    "                d += 1\n",
    "            if i > 0 and password[i] == password[i - 1]:\n",
    "                return False\n",
    "        if a == 0 or b == 0 or c == 0 or d == 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        boolean = [False]*4\n",
    "        special = {\"!\",\"@\",\"#\",\"$\",\"%\",\"^\",\"&\",\"*\",\"(\",\")\",\"-\",\"+\"}\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        for i in range(len(password)-1):\n",
    "            if password[i] == password[i+1]:\n",
    "                return False\n",
    "        for char in password:\n",
    "            if ord(char) in range(97,123):\n",
    "                boolean[0] = True\n",
    "            elif ord(char) in range(65,91):\n",
    "                boolean[1] = True\n",
    "            elif ord(char) in range(48,58):\n",
    "                boolean[2] = True\n",
    "            elif char in special:\n",
    "                boolean[3] = True\n",
    "        return boolean[0] and boolean[1] and boolean[2] and boolean[3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password)<8:\n",
    "            return False\n",
    "        s=[0 for i in range(4)]\n",
    "        k='/'\n",
    "        for a in password:\n",
    "            if a.islower():\n",
    "                s[0]=1\n",
    "            if a.isupper():\n",
    "                s[1]=1\n",
    "            if a.isdigit():\n",
    "                s[2]=1\n",
    "            if a in  \"!@#$%^&*()-+\":\n",
    "                s[3]=1\n",
    "            if a==k:\n",
    "                return False\n",
    "            k=a\n",
    "        return sum(s)==4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        chars = \"!@#$%^&*()-+\"\n",
    "        lower, upper, digit, char, contin = 0, 0, 0, 0, 0\n",
    "        for i in range(n):\n",
    "            if re.match(r'^[a-z]$', password[i]):\n",
    "                lower += 1\n",
    "            if re.match(r'^[A-Z]$', password[i]):\n",
    "                upper += 1\n",
    "            if password[i].isdigit():\n",
    "                digit += 1\n",
    "            if password[i] in chars:\n",
    "                char += 1\n",
    "            if i < n-1 and password[i] == password[i+1]:\n",
    "                return False\n",
    "        return bool(lower and upper and digit and char)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "            \n",
    "        for i in range(26):\n",
    "            if chr(ord('a') + i) in password:\n",
    "                break\n",
    "            if i == 25:\n",
    "                return False\n",
    "        \n",
    "        for i in range(26):\n",
    "            if chr(ord('A') + i) in password:\n",
    "                break\n",
    "            if i == 25:\n",
    "                return False\n",
    "        \n",
    "        for c in '!@#$%^&*()-+':\n",
    "            if c in password:\n",
    "                break\n",
    "            if c == '+':\n",
    "                return False\n",
    "        \n",
    "        for c in '0123456789':\n",
    "            if c in password:\n",
    "                break\n",
    "            if c == '9':\n",
    "                return False\n",
    "        \n",
    "        for c1, c2 in zip(password, password[1:]):\n",
    "            if c1 == c2:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        nums = set('1234567890')\n",
    "        spe = set(\"!@#$%^&*()-+\")\n",
    "        s = set(password)\n",
    "        ans = [0,0,0,0,1]\n",
    "\n",
    "        for i in range(len(password)):\n",
    "            ordi = ord(password[i])\n",
    "            if i != 0 and password[i] == last:\n",
    "                ans[4] = 0\n",
    "            if 97<=ordi<=124:\n",
    "                ans[0] = 1\n",
    "            elif 65<=ordi<=91:\n",
    "                ans[1] = 1\n",
    "            elif password[i] in nums:\n",
    "                ans[2] = 1\n",
    "            elif password[i] in spe:\n",
    "                ans[3] = 1\n",
    "\n",
    "            last = password[i]\n",
    "\n",
    "        return len(password) > 7 and ans == [1,1,1,1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        AA = '!@#$%^&*()-+'\n",
    "        if len(password) < 8:return False\n",
    "        a,b,c,d = 0,0,0,0\n",
    "        pre = '?'\n",
    "        for i in password:\n",
    "            if i == pre:return False\n",
    "            if 'a' <= i <= 'z':a = 1\n",
    "            if 'A' <= i <= 'Z':b = 1\n",
    "            if '0' <= i <= '9':c = 1\n",
    "            if i in AA:d = 1\n",
    "            pre = i\n",
    "        return bool(a and b and c and d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        # 按题意\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        specials = set(\"!@#$%^&*()-+\")\n",
    "        hasLower = hasUpper = hasDigit = hasSpecial = False\n",
    "\n",
    "        for i, ch in enumerate(password):\n",
    "            if i != len(password) - 1 and password[i] == password[i + 1]:\n",
    "                return False\n",
    "\n",
    "            if ch.islower():\n",
    "                hasLower = True\n",
    "            elif ch.isupper():\n",
    "                hasUpper = True\n",
    "            elif ch.isdigit():\n",
    "                hasDigit = True\n",
    "            elif ch in specials:\n",
    "                hasSpecial = True\n",
    "\n",
    "        return hasLower and hasUpper and hasDigit and hasSpecial\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        \"\"\"\n",
    "        小写字母 1\n",
    "        大写字母 1 << 1\n",
    "        数字 1 << 2\n",
    "        特殊字符 1 << 3\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        special_word = \"!@#$%^&*()-+\"\n",
    "        n = len(password)\n",
    "        if n < 8:\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if i + 1 < n and password[i] == password[i + 1]:\n",
    "                return False\n",
    "            elif 'a' <= password[i] <= 'z':\n",
    "                ans |= 1\n",
    "            elif 'A' <= password[i] <= 'Z':\n",
    "                ans |= 1 << 1\n",
    "            elif '0' <= password[i] <= '9':\n",
    "                ans |= 1 << 2\n",
    "            elif password[i] in special_word:\n",
    "                ans |= 1 << 3\n",
    "        \n",
    "        return ans == 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        nums = set('1234567890')\n",
    "        spe = set(\"!@#$%^&*()-+\")\n",
    "        s = set(password)\n",
    "        lenth = lower = upper = number = special = False\n",
    "        repeat = True\n",
    "        for i in range(len(password)):\n",
    "            ordi = ord(password[i])\n",
    "            if i != 0 and password[i] == last:\n",
    "                repeat = False\n",
    "            if 97<=ordi<=124:\n",
    "                lower = True\n",
    "            elif 65<=ordi<=91:\n",
    "                upper = True\n",
    "            elif password[i] in nums:\n",
    "                number = True\n",
    "            elif password[i] in spe:\n",
    "                special = True\n",
    "\n",
    "            last = password[i]\n",
    "\n",
    "        if len(password) > 7:\n",
    "            lenth = True\n",
    "        return lenth and repeat and lower and upper and number and special"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        n = len(password)\n",
    "        if n < 8: return False\n",
    "        flag1 = flag2 = flag3 = flag4 = 0\n",
    "        for i in range(n):\n",
    "            if '0' <= password[i] <= '9': flag3 = 1\n",
    "            if 'a' <= password[i] <= 'z': flag1 = 1\n",
    "            if 'A' <= password[i] <= 'Z': flag2 = 1\n",
    "            if password[i] in \"!@#$%^&*()-+\": flag4 = 1\n",
    "            if i > 0 and password[i] == password[i-1]: return False\n",
    "            \n",
    "        return flag1 == 1 and flag2 == 1 and flag3 == 1 and flag4 == 1\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        if len(password) < 8:\n",
    "            return False\n",
    "        tag_status = [False, False, False, False]\n",
    "        for index, p in enumerate(password):\n",
    "            if index != 0:\n",
    "                if p == password[index - 1]:\n",
    "                    return False\n",
    "            if '0' <= p <= '9':\n",
    "                tag_status[0] = True\n",
    "            elif 'a' <= p <= 'z':\n",
    "                tag_status[1] = True\n",
    "            elif 'A' <= p <= 'Z':\n",
    "                tag_status[2] = True\n",
    "            else:\n",
    "                tag_status[3] = True\n",
    "        return all(tag_status)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordCheckerII(self, password: str) -> bool:\n",
    "        s = password\n",
    "        if len(s) < 8: return False\n",
    "        \n",
    "        ok = False\n",
    "        for i in range(0, 26):\n",
    "            x = chr(ord('a') + i)\n",
    "            if x in s:\n",
    "                ok = True\n",
    "                break\n",
    "        if not ok: return False\n",
    "        \n",
    "        ok = False\n",
    "        for i in range(0, 26):\n",
    "            x = chr(ord('A') + i)\n",
    "            if x in s:\n",
    "                ok = True\n",
    "                break\n",
    "        if not ok: return False\n",
    "        \n",
    "        ok = False\n",
    "        for i in range(0, 10):\n",
    "            x = chr(ord('0') + i)\n",
    "            if x in s:\n",
    "                ok = True\n",
    "                break\n",
    "        if not ok: return False\n",
    "        \n",
    "        ok = False\n",
    "        for x in \"!@#$%^&*()-+\":\n",
    "            if x in s:\n",
    "                ok = True\n",
    "                break\n",
    "        if not ok: return False\n",
    "        \n",
    "        for i in range(0, len(s) - 1):\n",
    "            if s[i] == s[i + 1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a-1>=3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        return res  + max(0, n-20)+ max(sum(a//3 for _, a in pq), lack)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a>3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        return res + max(0, n-20) + max(sum(a//3 for _, a in pq), lack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        has_lower = has_highter = has_digit = False\n",
    "        for c in password:\n",
    "            if c.islower():\n",
    "                has_lower = True\n",
    "            if c.isupper():\n",
    "                has_highter = True\n",
    "            if c.isdigit():\n",
    "                has_digit = True\n",
    "        n = len(password)\n",
    "        que = (3-(has_digit + has_highter + has_lower))\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6-n, que)\n",
    "        if n >= 6 and n <= 20:\n",
    "            sum1 = 0 \n",
    "            tem = 1\n",
    "            for i in range(1, len(password)):\n",
    "                if password[i] == password[i-1]:\n",
    "                    tem += 1\n",
    "                else:\n",
    "                    sum1 += int(tem/3)\n",
    "                    tem = 1\n",
    "            sum1 += int(tem/3)\n",
    "            result = sum1\n",
    "        else:\n",
    "            dp = []\n",
    "            res = 0\n",
    "            for _ , g in groupby(password):\n",
    "                a = len(list(g))\n",
    "                if a >=3:\n",
    "                    heappush(dp, (a%3, a))\n",
    "            while dp and n >20 :\n",
    "                _ , a = heappop(dp)\n",
    "                if a > 3:\n",
    "                    heappush(dp, ((a-1)%3, a-1))\n",
    "                n -= 1\n",
    "                res += 1\n",
    "            result = res + max(0, n-20) + max(sum(a//3 for _, a in dp), que)\n",
    "        \n",
    "\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uppercaseCheck(self, password):\n",
    "        return 1 if not re.search(r'[A-Z]', password) else 0\n",
    "\n",
    "    def lowercaseCheck(self, password):\n",
    "        return 1 if not re.search(r'[a-z]', password) else 0\n",
    "\n",
    "    def numberCheck(self, password):\n",
    "        return  1 if not re.search(r'[0-9]', password) else 0\n",
    "    \n",
    "    # 检查同一字符连续出现三次及以上，并转换为次数 \"aaaaabbbbbbcc\" -> [5,6] 有个测试用例有.和！需要特殊处理\n",
    "    def lengthCheck(self, password):\n",
    "        res = []\n",
    "        for el in re.finditer(r'([\\\\.a-zA-Z0-9!])\\1{2,}', password):\n",
    "            # print('str found', el.start(), el.end())\n",
    "            res.append(el.end()-el.start())\n",
    "        return res\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        check_num = self.uppercaseCheck(password) + self.lowercaseCheck(password) + self.numberCheck(password)\n",
    "        res = self.lengthCheck(password)\n",
    "        # 连续多余的字符串替换\n",
    "        replace = sum(map(lambda x: int(x//3),res))\n",
    "        if n <= 5: \n",
    "            return max(check_num,6-n)\n",
    "        elif n <= 20:\n",
    "            return max(replace, check_num)\n",
    "        elif n > 20:\n",
    "            numdel = n - 20\n",
    "\n",
    "            # 多余的字符串删除\n",
    "            l = list(map(lambda x: (x % 3)+1,res))\n",
    "            l.sort()\n",
    "            rem = numdel\n",
    "            for i in range(0,len(l)):\n",
    "                if (rem >= l[i]):\n",
    "                    rem -= l[i]\n",
    "                    replace -= 1\n",
    "            replace -= int(rem / 3)\n",
    "\n",
    "            if replace < check_num: \n",
    "                replace = check_num\n",
    "                \n",
    "            return numdel + replace\n",
    "        return 0\n",
    "\n",
    "# 作者：int_64\n",
    "# 链接：https://leetcode.cn/problems/strong-password-checker/solutions/1387956/by-jam007-dcdd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a>3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        return res + max(0, n-20) + max(sum(a//3 for _, a in pq), lack)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "\n",
    "        categories = has_digit + has_lower + has_upper\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            replace, remove = 0, n - 20\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            rm2 += 1\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "\n",
    "            use3 = min(replace, remove //3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 2\n",
    "\n",
    "\n",
    "            return (n - 20) + max(replace, 3 - categories)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        \"\"\"\n",
    "        当前password长度为n,字符种类为m 有g段字母连续长度大于3 g[i]是第i个连续段的长度\n",
    "        if n<6: 只需要增加和替换操作 rs = max(6-n,3-m)\n",
    "        elif 6<=n<=20: 只需要替换操作，其余操作都可以通过替换达到目的 对于某一个k(连续字符长度) 需要k//3次 rs = max(sum(k//3),3-m)\n",
    "        else:只需要删除和替换操作，n-20是必不可少的，且删除操作可能会影响到替换操作，优先删除的一定是连续长度大于3的字符\n",
    "            来讨论一下k%3的情况\n",
    "            1.k%3=0 删除1个字符k//3会立马少一个，随后每删除3个再少一个\n",
    "            2.k%3=1 删除2个字符k//3会立马少一个，随后每删除3个再少一个\n",
    "            3.k%3=2 删除3个字符k//3会立马少一个，随后每删除3个再少一个\n",
    "            因此使用cnts数组，cnts[i]记录连续长不低于3的连续段中 长度余数为i的个数\n",
    "            显然再删除时 先考虑余数小的\n",
    "        \"\"\"\n",
    "        n = len(password)\n",
    "        a = b= c = 0 #3个种类\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                a = 1\n",
    "            elif ch.isupper():\n",
    "                b = 1\n",
    "            elif ch.isdigit():\n",
    "                c = 1\n",
    "        m = a+b+c\n",
    "        if n<6:\n",
    "            return max(6-n,3-m)\n",
    "        elif n<=20:\n",
    "            i = 0\n",
    "            tot  = 0 #记录需要处理的连续长度的次数\n",
    "            while i<n:\n",
    "                j = i\n",
    "                while j<n and password[i]==password[j]:\n",
    "                    j += 1\n",
    "                k = j-i\n",
    "                if k>=3:\n",
    "                    tot += k//3\n",
    "                i = j\n",
    "            return max(tot,3-m)\n",
    "        else:\n",
    "            tot = 0\n",
    "            cnts = [0 for _ in range(3)]\n",
    "            i = 0\n",
    "            while i<n:\n",
    "                j = i\n",
    "                while j<n and password[i]==password[j]:\n",
    "                    j += 1\n",
    "                k = j-i\n",
    "                if k>=3:\n",
    "                    tot += k//3\n",
    "                    cnts[k%3] += 1\n",
    "                i = j\n",
    "            num_delete = n-20 #需要删除的数量\n",
    "            for i in range(3):\n",
    "                if i==2:#为0 1的都处理完毕了 剩下的每3次删除就可以解决这个字符串\n",
    "                    cnts[i] = tot\n",
    "                if cnts[i]!=0 and num_delete!=0:\n",
    "                    tmp = min(cnts[i]*(i+1),num_delete)  #需要的删除次数 和实际的删除次数相比\n",
    "                    num_delete -= tmp\n",
    "                    tot -= tmp//(i+1)#删除可以抵消的替换操作\n",
    "            return n-20+max(tot,3-m)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        res = 0\n",
    "        n = len(password)\n",
    "        has_lower, has_upper, has_digit = False, False, False\n",
    "        for ch in password:\n",
    "            if ch.islower(): has_lower = True\n",
    "            elif ch.isupper(): has_upper = True\n",
    "            elif ch.isdigit(): has_digit = True\n",
    "\n",
    "        cnums = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n<6:\n",
    "            return max(6-n, 3-cnums)\n",
    "        elif n<=20:\n",
    "            replace,cnt = 0,0\n",
    "            cur = '#'\n",
    "            for ch in password:\n",
    "                if ch==cur:\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    replace += cnt//3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            replace += cnt//3\n",
    "            return max(replace, 3 - cnums)\n",
    "        else:\n",
    "            replace, remove = 0, n-20\n",
    "            rm2 = cnt = 0\n",
    "            cur = '#'\n",
    "\n",
    "            for ch in password:\n",
    "                if ch==cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove>0 and cnt>=3:\n",
    "                        if cnt%3==0:\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt%3 == 1:\n",
    "                            rm2 += 1\n",
    "                    replace += cnt//3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt>=3:\n",
    "                if cnt%3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt%3==1:\n",
    "                    rm2+=1\n",
    "            \n",
    "            replace += cnt//3\n",
    "\n",
    "            use2 = min(replace, rm2, remove//2)\n",
    "            replace -= use2\n",
    "            remove -= use2*2\n",
    "\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3*3\n",
    "            return (n-20)+max(replace, 3-cnums)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n=len(password)\n",
    "        if n<=4:\n",
    "            return 6-n\n",
    "        num,little,big=0,0,0\n",
    "        for ch in password:\n",
    "            if \"0\"<=ch<=\"9\":\n",
    "                num=1\n",
    "            if \"a\"<=ch<=\"z\":\n",
    "                little=1\n",
    "            if \"A\"<=ch<=\"Z\":\n",
    "                big=1\n",
    "        insert=3-(num+little+big)\n",
    "        i,j=0,0\n",
    "        ls=[]\n",
    "        while i<n and j<n:\n",
    "            while j<n and password[i]==password[j]:\n",
    "                j+=1\n",
    "            if j-i>=3:\n",
    "                ls.append(j-i)\n",
    "            i=j\n",
    "        if n<=20:\n",
    "            tp=0\n",
    "            for k in ls:\n",
    "                tp+=k//3\n",
    "            #print(tp,insert)\n",
    "            return max(tp,insert,6-n)\n",
    "        else:\n",
    "            ls.sort(reverse=True)\n",
    "            l=n-20\n",
    "            tpl=[]\n",
    "            tp=0\n",
    "            c2=0 \n",
    "            for k in ls:\n",
    "                tp+=k//3\n",
    "                if k%3==0:\n",
    "                    if l>0:\n",
    "                        l-=1\n",
    "                        tp-=1\n",
    "                elif k%3==1:\n",
    "                    c2+=1\n",
    "            print(l,tp)\n",
    "            while l>0:\n",
    "                if c2>0 and l>=2:\n",
    "                    l-=2\n",
    "                    tp-=1\n",
    "                elif l>=3:\n",
    "                    l-=3\n",
    "                    tp-=1\n",
    "                else:\n",
    "                    l=0\n",
    "            tp=max(0,tp)\n",
    "            print(tp)\n",
    "            return n-20+max(tp,insert)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # 1. we want to check if there are some missing requirements, 3 cases\n",
    "\n",
    "        # 2. we want to check if there are only <6 letters, we need to add more\n",
    "\n",
    "        # 3. if more than 20 characters or have consecutive letters\n",
    "\n",
    "        n = len(password)\n",
    "\n",
    "        missing = 3 - sum(bool(re.search(reg, password)) for reg in ['[A-Z]', '[a-z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, missing) # has to reach 6 in any ways\n",
    "        \n",
    "        # we add all letters in priority queue, heap in python\n",
    "        # we record the remainer, if remainder == 0, meaning at least there are three letters, we want to delete these first\n",
    "        q = []\n",
    "        heapify(q)\n",
    "        for _, group_letter in groupby(password): # group letters into separated strings in a list, we only need to check if they are greater or equal to 3. This is different than counting as aaabbbaa can be seprated in 3 different groups.\n",
    "\n",
    "            group_len = len(list(group_letter))\n",
    "            if group_len >= 3:\n",
    "                remainder = group_len % 3\n",
    "                heappush(q, (remainder, group_len))\n",
    "            \n",
    "\n",
    "            res = 0\n",
    "        # we only need to consider more than 20 cases and the case with missing as \n",
    "        while q and n > 20:\n",
    "            cur_remainder, cur_len = heappop(q)\n",
    "\n",
    "            if cur_len - 1 >= 3:\n",
    "                heappush(q, ((cur_len-1)%3, cur_len-1))\n",
    "            \n",
    "            n -= 1\n",
    "            res += 1\n",
    "\n",
    "        \n",
    "        # after removal, we should have a valid length, now we need to handle the missing condition and the remaining letters that have more than 3 letters\n",
    "\n",
    "        # we firstly deal with more than 3 letters\n",
    "        # for k length, we just need k//3 number of replacements\n",
    "        # replacements for all remaining ones in heap we count number and compare it with missing (if it is less than missing we need to make missing number of changes as we want the password to be valid, otherwise, we can )\n",
    "        mixup = 0\n",
    "        while q:\n",
    "            _, cur_len = heappop(q)\n",
    "\n",
    "            mixup += cur_len // 3\n",
    "        \n",
    "        res += max(missing, mixup)\n",
    "\n",
    "            \n",
    "        return res +  max(0, n-20)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        \n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a-1>=3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        print(res, sum(a//3 for _, a in pq), lack)\n",
    "        return res  + max(0, n-20)+ max(sum(a//3 for _, a in pq), lack)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a>3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        return res + max(0, n-20) + max(sum(a//3 for _, a in pq), lack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        # 先检查是否包含小写字母，大写字母，数据\n",
    "        s = password\n",
    "        has_lower, has_upper, has_num = 0, 0, 0\n",
    "        for ch in s:\n",
    "            if ch.isnumeric():\n",
    "                has_num = 1\n",
    "            elif ch.isupper():\n",
    "                has_upper = 1\n",
    "            elif ch.islower():\n",
    "                has_lower = 1\n",
    "\n",
    "        # 处理字符长度\n",
    "        if len(s) < 6:\n",
    "            # 总长度不到6时候，肯定至少补一次字符，补自字符同时就可以\n",
    "            # 把连续的3个字符打断，最长只可能5个连续字符，插入一次字符\n",
    "            # 就可以完成分割，所以只需要关注字符种类够不够，假设缺少Ncat\n",
    "            # 种字符，那就需要添加max(len(s) - 6, Ncat)个字符满足要求\n",
    "            return max(3 - has_lower - has_num - has_upper, 6 - len(s))\n",
    "        elif len(s) <= 20:\n",
    "            # 这种情况不需要考虑长度问题，长度已经符合条件了，对于破坏三个连续字符这个操作而言，修改\n",
    "            # 字符是开销最小的，连续n个字符连续，只需要每3个把最后一个字符修改成不一样的字符即可，总共\n",
    "            # 修改n // 3\n",
    "            # 次，而且还不会影响字符串长度，对于字符类型不足的问题，也可以通过修改字符来满足条件\n",
    "            # 所以修改字符这个操作可以同时对3字符连续和字符种类不足两种错误进行修正，且不会造成字符串\n",
    "            # 长度问题，假设连续字符问题总共需要修改Nseq次满足要求，字符种类不足问题总共需要修改Ncat次\n",
    "            # 才能满足要求，那最佳修改方案就是max(Nseq, Ncat)\n",
    "            # 次修改满足题目题目要求\n",
    "            i = 0\n",
    "            Nsep = 0\n",
    "            while i < len(s):\n",
    "                j = i\n",
    "                while j < len(s) and s[j] == s[i]:\n",
    "                    j += 1\n",
    "                if j - i >= 3:\n",
    "                    Nsep += (j - i) // 3\n",
    "                i = j\n",
    "            return max(3 - has_lower - has_upper - has_num, Nsep)\n",
    "        else:\n",
    "            \"\"\"\n",
    "               对于字符串长度大于20的情况，最少会有len(s) - 20 次删除的操作，这些删除操作是节约不掉的\n",
    "            删除不可能解决字符类型不足的问题但是可能解决3个连续字符的问题，所以删除时候尽量让3个连续\n",
    "            字符问题多得到解决，这样在字符串长度减少到20个时候，继续解决3个连续字符的问题和字符种类\n",
    "            不足的问题时候，剩下操作次数就最少\n",
    "\n",
    "            考虑n个连续的字符，n%3 == 0 的情况下, 只要删掉尾巴上的字符，就可以解决一个3字符连续问题，\n",
    "            转变成n%3 == 2的状态，\n",
    "            n%3 == 1 的情况，需要删除2个字符才能减少一个3字符连续问题，转变成n%3 == 0状态\n",
    "            n%3 == 2时候，需要删除3个字符才能减少一个三字符连续问题，转变成n%3 == 1状态\n",
    "            所以对于连续3字符问题，需要按照这个优先级来进行处理，直到剩余字符为20个\n",
    "            删除字符时候一定能找到不会让字符种类数减少的方式进行删除，所以不需要考虑字符类型不足的问题\n",
    "            等字符数量减到20个的时候，再通过修改字符的方式来和3字符连续的问题一起解决 \n",
    "            \"\"\"\n",
    "            del_cnt = len(s) - 20\n",
    "\n",
    "            # 先删除， 删除重复的S\n",
    "            # 改 aaa -> 删=1 改=1\n",
    "            # 改 aaa a -> 删=2；改=1\n",
    "            # 改 aaa aaa -> 删=4 改=2\n",
    "            # 改 aaa aa -> 删=3 改=1\n",
    "            # 删  lens(s) -20\n",
    "            # 大小写 3 - has_lower - has_upper - has_num\n",
    "            rep = []\n",
    "            i = 0\n",
    "            Nsep = 0\n",
    "            while i < len(s):\n",
    "                j = i\n",
    "                while j < len(s) and s[j] == s[i]:\n",
    "                    j += 1\n",
    "                if j - i >= 3:\n",
    "                    Nsep += (j - i) // 3\n",
    "                    heappush(rep,((j - i)%3,(j - i)//3))\n",
    "                i = j\n",
    "\n",
    "            count = 0  ## 删除掉的字符可以抵消replace的次数\n",
    "            while rep and rep[0][0] + 1 <= del_cnt:\n",
    "                re,qe = heappop(rep)\n",
    "                count += 1\n",
    "                del_cnt -= 1 + re\n",
    "                if qe > 0:\n",
    "                    heappush(rep, (2, qe - 1))\n",
    "            return  len(s) - 20 + max(Nsep - count, 3 - has_lower - has_upper - has_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        #copy\n",
    "        n = len(password)\n",
    "        lack = 3-sum(bool(re.search(reg,password)) for reg in ['[a-z]','[A-Z]','[0-9]'])\n",
    "        if n <6:\n",
    "            return max(6-n,lack)\n",
    "        pq = []\n",
    "        for _,g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a >= 3:\n",
    "                heappush(pq,(a%3,a))\n",
    "        res = 0\n",
    "        while pq and n >20:\n",
    "            _,a = heappop(pq)\n",
    "            if a >3:\n",
    "                heappush(pq,((a-1)%3,a-1))\n",
    "            n -=1\n",
    "            res +=1\n",
    "        return res + max(0,n-20) + max(sum(a//3 for _,a in pq),lack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            # 替换次数和删除次数\n",
    "            replace, remove = 0, n - 20\n",
    "            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            # 如果是 k % 3 = 1 的组，那么存下来备用\n",
    "                            rm2 += 1\n",
    "                        # k % 3 = 2 的组无需显式考虑\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        s = password\n",
    "        missing_type = 3\n",
    "        if any('a' <= c <= 'z' for c in s):\n",
    "            missing_type -= 1\n",
    "        if any('A' <= c <= 'Z' for c in s):\n",
    "            missing_type -= 1\n",
    "        if any(c.isdigit() for c in s):\n",
    "            missing_type -= 1\n",
    "\n",
    "        n = len(s)\n",
    "        change = 0\n",
    "        one = two = 0\n",
    "        p = 2\n",
    "        while p < n:\n",
    "            if s[p] == s[p-1] == s[p-2]:\n",
    "                length = 2\n",
    "                while p < n and s[p] == s[p-1]:\n",
    "                    length += 1\n",
    "                    p += 1\n",
    "\n",
    "                change += length // 3\n",
    "                if length % 3 == 0:\n",
    "                    one += 1\n",
    "                elif length % 3 == 1:\n",
    "                    two += 1\n",
    "            else:\n",
    "                p += 1\n",
    "\n",
    "        if n < 6:\n",
    "            return max(missing_type, 6 - n)\n",
    "        elif n <= 20:\n",
    "            return max(missing_type, change)\n",
    "        else:\n",
    "            delete = n - 20\n",
    "\n",
    "            change -= min(delete, one * 1) // 1\n",
    "            change -= min(max(delete - one, 0), two * 2) // 2\n",
    "            change -= max(delete - one - 2 * two, 0) // 3\n",
    "\n",
    "            return delete + max(missing_type, change)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for c in password:\n",
    "            if c.islower():\n",
    "                has_lower = True\n",
    "            if c.isupper():\n",
    "                has_upper = True\n",
    "            if c.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower+has_upper+has_digit\n",
    "\n",
    "        if n<6:\n",
    "            return max(6-n,3-categories)\n",
    "\n",
    "        elif n<=20:\n",
    "            replace = cnt = 0\n",
    "            cur = '#'\n",
    "            for c in password:\n",
    "                if c == cur:\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    replace+=cnt//3\n",
    "                    cnt=1\n",
    "                    cur=c\n",
    "            replace += cnt//3\n",
    "            return max(replace,3-categories)\n",
    "        else:\n",
    "            replace,remove = 0,n-20\n",
    "            rm2 = cnt = 0\n",
    "            cur = '#'\n",
    "\n",
    "            for c in password:\n",
    "                if c == cur:\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    if remove>0 and cnt>=3:\n",
    "                        if cnt%3==0:\n",
    "                            remove-=1\n",
    "                            replace-=1\n",
    "                        elif cnt%3==1:\n",
    "                            rm2+=1\n",
    "                    replace+=cnt//3\n",
    "                    cnt =1\n",
    "                    cur=c\n",
    "            if remove>0 and cnt>=3:\n",
    "                if cnt%3==0:\n",
    "                    remove-=1\n",
    "                    replace-=1\n",
    "                elif cnt%3==1:\n",
    "                    rm2+=1\n",
    "            replace += cnt//3\n",
    "\n",
    "            use2 = min(replace,rm2,remove//2)\n",
    "            replace-=use2\n",
    "            remove-=use2*2\n",
    "            use3=min(replace,remove//3)\n",
    "            replace-=use3\n",
    "            remove-=use3*3\n",
    "            return (n-20)+max(replace,3-categories)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # 1. we want to check if there are some missing requirements, 3 cases\n",
    "\n",
    "        # 2. we want to check if there are only <6 letters, we need to add more\n",
    "\n",
    "        # 3. if more than 20 characters or have consecutive letters\n",
    "\n",
    "        n = len(password)\n",
    "\n",
    "        missing = 3 - sum(bool(re.search(reg, password)) for reg in ['[A-Z]', '[a-z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, missing) # has to reach 6 in any ways\n",
    "        \n",
    "        # we add all letters in priority queue, heap in python\n",
    "        # we record the remainer, if remainder == 0, meaning at least there are three letters, we want to delete these first\n",
    "        q = []\n",
    "        heapify(q)\n",
    "        for _, group_letter in groupby(password): # group letters into separated strings in a list, we only need to check if they are greater or equal to 3. This is different than counting as aaabbbaa can be seprated in 3 different groups.\n",
    "\n",
    "            group_len = len(list(group_letter))\n",
    "            if group_len >= 3:\n",
    "                remainder = group_len % 3\n",
    "                heappush(q, (remainder, group_len))\n",
    "            \n",
    "\n",
    "            res = 0\n",
    "        # we only need to consider more than 20 cases and the case with missing as \n",
    "        while q and n > 20:\n",
    "            cur_remainder, cur_len = heappop(q)\n",
    "\n",
    "            if cur_len - 1 >= 3:\n",
    "                heappush(q, ((cur_len-1)%3, cur_len-1))\n",
    "            \n",
    "            n -= 1\n",
    "            res += 1\n",
    "\n",
    "        \n",
    "        # after removal, we should have a valid length, now we need to handle the missing condition and the remaining letters that have more than 3 letters\n",
    "\n",
    "        # we firstly deal with more than 3 letters\n",
    "        # for k length, we just need k//3 number of replacements\n",
    "        # replacements for all remaining ones in heap we count number and compare it with missing (if it is less than missing we need to make missing number of changes as we want the password to be valid, otherwise, we can )\n",
    "        mixup = 0\n",
    "        while q:\n",
    "            _, cur_len = heappop(q)\n",
    "\n",
    "            mixup += cur_len // 3\n",
    "        \n",
    "        res += max(missing, mixup)\n",
    "\n",
    "            \n",
    "        return res +  max(0, n-20)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        \n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a-1>=3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        print(res, sum(a//3 for _, a in pq), lack)\n",
    "        return res  + max(0, n-20)+ max(sum(a//3 for _, a in pq), lack)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "\n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "\n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "\n",
    "            replace, remove = 0, n - 20\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            rm2 += 1\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "\n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "\n",
    "            replace += cnt // 3\n",
    "\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        cnt = digit = upper = lower = 0\n",
    "        series = []\n",
    "        foo = [3] * 16\n",
    "        for i, c in enumerate(password):\n",
    "            if i and c == password[i - 1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if cnt >= 3:\n",
    "                    series.append(cnt)\n",
    "                cnt = 1\n",
    "            if c.isdigit():\n",
    "                digit = 1\n",
    "            elif c.isupper():\n",
    "                upper = 1\n",
    "            elif c.islower():\n",
    "                lower = 1\n",
    "        if cnt >= 3:\n",
    "            series.append(cnt)\n",
    "        for x in series:\n",
    "                foo.append(x % 3 + 1)\n",
    "        foo.sort(reverse=True)\n",
    "        c1 = sum(x // 3 for x in series)\n",
    "        c2 = 3 - upper - digit - lower\n",
    "        c3 = len(password)\n",
    "        if c3 < 6:\n",
    "            return max(6 - c3, c1, c2)\n",
    "        elif c3 > 20:\n",
    "            t = c3 - 20\n",
    "            s = 0\n",
    "            while foo and foo[-1] <= t:\n",
    "                t -= foo.pop()\n",
    "                s += 1\n",
    "            c1 = max(0, c1 - s)\n",
    "            return c3 - 20 + max(c1, c2)\n",
    "        return max(c1, c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            # 替换次数和删除次数\n",
    "            replace, remove = 0, n - 20\n",
    "            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            # 如果是 k % 3 = 1 的组，那么存下来备用\n",
    "                            rm2 += 1\n",
    "                        # k % 3 = 2 的组无需显式考虑\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        s = password\n",
    "        missing_type = 3\n",
    "        if any('a' <= c <= 'z' for c in s):\n",
    "            missing_type -= 1\n",
    "        if any('A' <= c <= 'Z' for c in s):\n",
    "            missing_type -= 1\n",
    "        if any(c.isdigit() for c in s):\n",
    "            missing_type -= 1\n",
    "\n",
    "        n = len(s)\n",
    "        change = 0\n",
    "        one = two = 0\n",
    "        p = 2\n",
    "        while p < n:\n",
    "            if s[p] == s[p-1] == s[p-2]:\n",
    "                length = 2\n",
    "                while p < n and s[p] == s[p-1]:\n",
    "                    length += 1\n",
    "                    p += 1\n",
    "\n",
    "                change += length // 3\n",
    "                if length % 3 == 0:\n",
    "                    one += 1\n",
    "                elif length % 3 == 1:\n",
    "                    two += 1\n",
    "            else:\n",
    "                p += 1\n",
    "\n",
    "        if n < 6:\n",
    "            return max(missing_type, 6 - n)\n",
    "        elif n <= 20:\n",
    "            return max(missing_type, change)\n",
    "        else:\n",
    "            delete = n - 20\n",
    "\n",
    "            change -= min(delete, one * 1) // 1\n",
    "            change -= min(max(delete - one, 0), two * 2) // 2\n",
    "            change -= max(delete - one - 2 * two, 0) // 3\n",
    "\n",
    "            return delete + max(missing_type, change)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            # 替换次数和删除次数\n",
    "            replace, remove = 0, n - 20\n",
    "            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            # 如果是 k % 3 = 1 的组，那么存下来备用\n",
    "                            rm2 += 1\n",
    "                        # k % 3 = 2 的组无需显式考虑\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "\n",
    "        n = len(password)\n",
    "        lack = 3 - sum(bool(re.search(reg, password)) for reg in ['[a-z]', '[A-Z]', '[0-9]'])\n",
    "        if n < 6:\n",
    "            return max(6-n, lack)\n",
    "        pq = []\n",
    "        for _, g in groupby(password):\n",
    "            a = len(list(g))\n",
    "            if a>=3:\n",
    "                heappush(pq, (a%3, a))\n",
    "        res = 0\n",
    "        while pq and n>20:\n",
    "            _, a = heappop(pq)\n",
    "            if a-1>=3:\n",
    "                heappush(pq, ((a-1)%3, a-1))\n",
    "            n -= 1\n",
    "            res += 1\n",
    "        return res  + max(0, n-20)+ max(sum(a//3 for _, a in pq), lack)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            # 替换次数和删除次数\n",
    "            replace, remove = 0, n - 20\n",
    "            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            # 如果是 k % 3 = 1 的组，那么存下来备用\n",
    "                            rm2 += 1\n",
    "                        # k % 3 = 2 的组无需显式考虑\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        lower, upper, digit = 0, 0, 0\n",
    "        for c in password:\n",
    "            if c.islower():\n",
    "                lower = 1 \n",
    "            if c.isupper():\n",
    "                upper = 1 \n",
    "            if c.isdigit():\n",
    "                digit = 1 \n",
    "        need = 3 - lower - upper - digit \n",
    "        if n < 6:\n",
    "            return max(6 - n, need)\n",
    "        elif n <= 20:\n",
    "            cnt_replace = 0\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                j = i \n",
    "                while j < n and password[j] == password[i]:\n",
    "                    j += 1 \n",
    "                if j - i >= 3:\n",
    "                    cnt_replace += (j - i) // 3 \n",
    "                i = j\n",
    "            return max(cnt_replace, need)\n",
    "        else:\n",
    "            cnt_delete = n - 20 \n",
    "            heap = []\n",
    "            i = 0\n",
    "            while i < n:\n",
    "                j = i \n",
    "                while j < n and password[j] == password[i]:\n",
    "                    j += 1 \n",
    "                if j - i >= 3:\n",
    "                    heapq.heappush(heap, [(j - i) % 3, j - i])\n",
    "                i = j\n",
    "            for i in range(cnt_delete):\n",
    "                if not heap:\n",
    "                    break\n",
    "                m, l = heapq.heappop(heap)\n",
    "                if l > 3:\n",
    "                    heapq.heappush(heap, [(m - 1) % 3, l - 1])\n",
    "            cnt_replace = 0\n",
    "            while heap:\n",
    "                m, l = heapq.heappop(heap)\n",
    "                cnt_replace += l // 3 \n",
    "            return cnt_delete + max(need, cnt_replace)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        n = len(password)\n",
    "        has_lower = has_upper = has_digit = False\n",
    "        for ch in password:\n",
    "            if ch.islower():\n",
    "                has_lower = True\n",
    "            elif ch.isupper():\n",
    "                has_upper = True\n",
    "            elif ch.isdigit():\n",
    "                has_digit = True\n",
    "        \n",
    "        categories = has_lower + has_upper + has_digit\n",
    "\n",
    "        if n < 6:\n",
    "            return max(6 - n, 3 - categories)\n",
    "        elif n <= 20:\n",
    "            replace = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            replace += cnt // 3\n",
    "            return max(replace, 3 - categories)\n",
    "        else:\n",
    "            # 替换次数和删除次数\n",
    "            replace, remove = 0, n - 20\n",
    "            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作\n",
    "            rm2 = cnt = 0\n",
    "            cur = \"#\"\n",
    "\n",
    "            for ch in password:\n",
    "                if ch == cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    if remove > 0 and cnt >= 3:\n",
    "                        if cnt % 3 == 0:\n",
    "                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作\n",
    "                            remove -= 1\n",
    "                            replace -= 1\n",
    "                        elif cnt % 3 == 1:\n",
    "                            # 如果是 k % 3 = 1 的组，那么存下来备用\n",
    "                            rm2 += 1\n",
    "                        # k % 3 = 2 的组无需显式考虑\n",
    "                    replace += cnt // 3\n",
    "                    cnt = 1\n",
    "                    cur = ch\n",
    "            \n",
    "            if remove > 0 and cnt >= 3:\n",
    "                if cnt % 3 == 0:\n",
    "                    remove -= 1\n",
    "                    replace -= 1\n",
    "                elif cnt % 3 == 1:\n",
    "                    rm2 += 1\n",
    "            \n",
    "            replace += cnt // 3\n",
    "\n",
    "            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定\n",
    "            use2 = min(replace, rm2, remove // 2)\n",
    "            replace -= use2\n",
    "            remove -= use2 * 2\n",
    "            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量\n",
    "            use3 = min(replace, remove // 3)\n",
    "            replace -= use3\n",
    "            remove -= use3 * 3\n",
    "            return (n - 20) + max(replace, 3 - categories)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def strongPasswordChecker(self, password: str) -> int:\n",
    "        i = 0\n",
    "        p = password\n",
    "        n = len(password)\n",
    "        lo, up, d = 1, 1, 1\n",
    "        rp = [] \n",
    "        while i < n:\n",
    "            if ord('0') <= ord(p[i]) <= ord('9'):\n",
    "                d = 0\n",
    "            elif ord('a') <= ord(p[i]) <= ord('z'):\n",
    "                lo = 0\n",
    "            elif ord('A') <= ord(p[i]) <= ord('Z'):\n",
    "                up = 0\n",
    "            j = i\n",
    "            while j < n and p[j] == p[i]:\n",
    "                j += 1\n",
    "            if j - i >= 3:\n",
    "                rp.append(j - i)\n",
    "                i = j \n",
    "            else:\n",
    "                i += 1\n",
    "        mis_ch = d + lo + up\n",
    "        l = len(p)\n",
    "        # print(f'{mis_ch}, rp={rp}')\n",
    "        if l < 6:\n",
    "            return max(6 - l, mis_ch) \n",
    "        elif 6 <= l <= 20:\n",
    "            return max(mis_ch, sum(x//3 for x in rp))\n",
    "        else:\n",
    "            ops = l - 20\n",
    "            print(f'rp={rp}, ops = {ops}')\n",
    "            tot = ops\n",
    "            while tot > 0 and sum(rp) > 0:\n",
    "                # rp.sort(key=lambda x:(x%3,-x))\n",
    "                rp.sort(key=lambda x:x%3)\n",
    "                for i, x in enumerate(rp):\n",
    "                    mn = min((rp[i]%3) + 1, tot)\n",
    "                    rp[i] -= mn\n",
    "                    tot -= mn\n",
    "                    if tot == 0:\n",
    "                        break\n",
    "            print(f'rp after del ={rp}')\n",
    "            return ops + max(mis_ch, sum(x//3 for x in rp))\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
